package demo2;


import demo1.SingleLinkedList;

public class Linkedlist {
     class Linklist {
          public int val;
          public Linklist next;
          public Linklist prev;

          public Linklist(int val) {
               this.val = val;
          }

     }

     public Linkedlist.Linklist head;
     public void MyLinkedlist() {
          Linkedlist.Linklist node1 = new Linkedlist.Linklist(1);
          Linkedlist.Linklist node2 = new Linkedlist.Linklist(2);
          Linkedlist.Linklist node3 = new Linkedlist.Linklist(3);
          Linkedlist.Linklist node4 = new Linkedlist.Linklist(4);
          Linkedlist.Linklist node5 = new Linkedlist.Linklist(5);

          node1.next = node2;
          node2.next = node3;
          node3.next = node4;
          node4.next = node5;

          node5.prev = node4;
          node4.prev = node3;
          node3.prev = node2;
          node2.prev = node1;

          this.head = node1;

     }
     //头插法
     public void addFirst(int data){
          Linklist cur = this.head;
          Linklist node = new Linklist(data);
          node.next = cur;
          cur.prev = node;
          this.head = node;
     }
     //尾插法
     public void addLast(int data){
          Linklist cur = this.head;
          Linklist node = new Linklist(data);
          if (cur == null) {
               this.head = node;
          }
          while(cur.next!= null) {
               cur = cur.next;
          }
          cur.next = node;
          node.prev = cur;

     }
     //任意位置插入,第一个数据节点为0号下标
     public void addIndex(int index,int data){

          if (index < 0 || index > size()) {
               System.out.println("该数不满足要求");
          }

          if (index == 0) {
               addFirst(data);
          }
          if (index == size()) {
               addLast(data);
          }

          Linklist cur = searchprev(index);
          Linklist node = new Linklist(data);

          node.next = cur.next;
          cur.next = node;
          node.prev = cur;

     }
     private Linklist searchprev(int index) {
          Linklist cur = this.head;
          while (index-1 != 0){
               cur = cur.next;
               index--;
          }
          return cur;
     }

     //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key){
          Linklist cur = this.head;

          while (cur.next != null) {
               if (cur.val == key) {
                    return true;
               }
               cur = cur.next;
          }

          return false;
     }

     //删除第一次出现关键字为key的节点
     public void remove(int key){
          if (this.head.val == key) {
               this.head = this.head.next;
               head.prev = null;
          }
          // 1.找到前驱
          Linklist cur = findprev(key);
          // 2.判断赋值是否为空
          if(cur == null) {
               System.out.println("该数字不存在");
          }
          // 3.删除
          Linklist del = cur.next;
          del.next.prev = cur;
          cur.next = del.next;

     }
     /**
      * 找到key关键字前一个节点所在位置
      * @param key
      * @return
      * */
     private  Linklist findprev(int key) {

          Linklist cur = this.head;
          while(cur.next != null){
               if(cur.next.val == key){
                    return cur;
               }
               cur = cur.next;
          }
          return null;
     }

     //删除所有值为key的节点
     public void removeAllKey(int key){

          if (head == null) {
               return;
          }
          if (head.val == key) {
               head.next.prev = null;
               head = head.next;
          }
          Linklist pre = head;
          Linklist cur = pre.next;
          while(cur != null) {
               if (cur.val == key) {
                    cur.next.prev =pre;
                    pre.next = cur.next;
                    cur = cur.next;
               }else{
                    pre = cur;
                    cur = cur.next;
               }
          }
     }

     //得到单链表的长度
     public int size(){
          int flg = 0;
          Linklist cur = this.head;
          while(cur != null){
               flg++;
               cur = cur.next;
          }
          return flg;
     }
     public void display(){
          Linklist cur = this.head;
          while(cur != null){
               System.out.println("cur = " + cur);
               cur = cur.next;
          }
     }
     public void clear(){
          Linklist cur = head;
          while(cur.next != null) {
               Linklist ser = cur.next;
               cur.val = 0;
               cur.next = null;
               cur.prev = null;
               cur = ser;
          }
          head = null;
     }
 }